{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "cd253c91",
   "metadata": {},
   "outputs": [],
   "source": [
    "%use fuel(2.3.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "db42ba10",
   "metadata": {},
   "outputs": [],
   "source": [
    "val envs = java.io.File(\"../../.env\")\n",
    "    .readLines()\n",
    "    .map {\n",
    "        it.split(\"=\")[0] to it.split(\"=\")[1].trim('\"')\n",
    "    }.toMap()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "abfcb68d",
   "metadata": {},
   "outputs": [],
   "source": [
    "val session = envs.get(\"AOC_SESSION\")\n",
    "val year = 2021\n",
    "val day = 19"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "2bd9cf7d",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun getInput(year: Int, day: Int, session: String): String {\n",
    "    val (_, _, result) = \"https://adventofcode.com/$year/day/$day/input\"\n",
    "    .httpGet()\n",
    "    .header(\"cookie\" to \"session=$session\")\n",
    "    .responseString()\n",
    "        \n",
    "    return result.get().trim()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "5b9ad572",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun submitAnswer(year: Int, day: Int, session: String, level: Int, answer: String): String {\n",
    "    val (_, _, result) = Fuel\n",
    "    .post(\n",
    "        \"https://adventofcode.com/$year/day/$day/answer\", \n",
    "        parameters = listOf(\"level\" to level, \"answer\" to answer))\n",
    "    .header(\"cookie\" to \"session=$session\")\n",
    "    .responseString()\n",
    "        \n",
    "    return result.get()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c4861e1a",
   "metadata": {},
   "outputs": [],
   "source": [
    "val sample = \"\"\"--- scanner 0 ---\n",
    "404,-588,-901\n",
    "528,-643,409\n",
    "-838,591,734\n",
    "390,-675,-793\n",
    "-537,-823,-458\n",
    "-485,-357,347\n",
    "-345,-311,381\n",
    "-661,-816,-575\n",
    "-876,649,763\n",
    "-618,-824,-621\n",
    "553,345,-567\n",
    "474,580,667\n",
    "-447,-329,318\n",
    "-584,868,-557\n",
    "544,-627,-890\n",
    "564,392,-477\n",
    "455,729,728\n",
    "-892,524,684\n",
    "-689,845,-530\n",
    "423,-701,434\n",
    "7,-33,-71\n",
    "630,319,-379\n",
    "443,580,662\n",
    "-789,900,-551\n",
    "459,-707,401\n",
    "\n",
    "--- scanner 1 ---\n",
    "686,422,578\n",
    "605,423,415\n",
    "515,917,-361\n",
    "-336,658,858\n",
    "95,138,22\n",
    "-476,619,847\n",
    "-340,-569,-846\n",
    "567,-361,727\n",
    "-460,603,-452\n",
    "669,-402,600\n",
    "729,430,532\n",
    "-500,-761,534\n",
    "-322,571,750\n",
    "-466,-666,-811\n",
    "-429,-592,574\n",
    "-355,545,-477\n",
    "703,-491,-529\n",
    "-328,-685,520\n",
    "413,935,-424\n",
    "-391,539,-444\n",
    "586,-435,557\n",
    "-364,-763,-893\n",
    "807,-499,-711\n",
    "755,-354,-619\n",
    "553,889,-390\n",
    "\n",
    "--- scanner 2 ---\n",
    "649,640,665\n",
    "682,-795,504\n",
    "-784,533,-524\n",
    "-644,584,-595\n",
    "-588,-843,648\n",
    "-30,6,44\n",
    "-674,560,763\n",
    "500,723,-460\n",
    "609,671,-379\n",
    "-555,-800,653\n",
    "-675,-892,-343\n",
    "697,-426,-610\n",
    "578,704,681\n",
    "493,664,-388\n",
    "-671,-858,530\n",
    "-667,343,800\n",
    "571,-461,-707\n",
    "-138,-166,112\n",
    "-889,563,-600\n",
    "646,-828,498\n",
    "640,759,510\n",
    "-630,509,768\n",
    "-681,-892,-333\n",
    "673,-379,-804\n",
    "-742,-814,-386\n",
    "577,-820,562\n",
    "\n",
    "--- scanner 3 ---\n",
    "-589,542,597\n",
    "605,-692,669\n",
    "-500,565,-823\n",
    "-660,373,557\n",
    "-458,-679,-417\n",
    "-488,449,543\n",
    "-626,468,-788\n",
    "338,-750,-386\n",
    "528,-832,-391\n",
    "562,-778,733\n",
    "-938,-730,414\n",
    "543,643,-506\n",
    "-524,371,-870\n",
    "407,773,750\n",
    "-104,29,83\n",
    "378,-903,-323\n",
    "-778,-728,485\n",
    "426,699,580\n",
    "-438,-605,-362\n",
    "-469,-447,-387\n",
    "509,732,623\n",
    "647,635,-688\n",
    "-868,-804,481\n",
    "614,-800,639\n",
    "595,780,-596\n",
    "\n",
    "--- scanner 4 ---\n",
    "727,592,562\n",
    "-293,-554,779\n",
    "441,611,-461\n",
    "-714,465,-776\n",
    "-743,427,-804\n",
    "-660,-479,-426\n",
    "832,-632,460\n",
    "927,-485,-438\n",
    "408,393,-506\n",
    "466,436,-512\n",
    "110,16,151\n",
    "-258,-428,682\n",
    "-393,719,612\n",
    "-211,-452,876\n",
    "808,-476,-593\n",
    "-575,615,604\n",
    "-485,667,467\n",
    "-680,325,-822\n",
    "-627,-443,-432\n",
    "872,-547,-609\n",
    "833,512,582\n",
    "807,604,487\n",
    "839,-516,451\n",
    "891,-625,532\n",
    "-652,-548,-490\n",
    "30,-46,-14\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "22a2c8c8",
   "metadata": {},
   "outputs": [],
   "source": [
    "val input = getInput(year, day, session)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "091eaf39",
   "metadata": {},
   "outputs": [],
   "source": [
    "fun solve(input: String): String {\n",
    "    val scanners = input\n",
    "        .split(Regex(\"\"\"--- scanner \\d+ ---\\n\"\"\"))\n",
    "        .drop(1)\n",
    "        .map {\n",
    "            it\n",
    "                .split(\"\\n\")\n",
    "                .filter { it.length > 0 }\n",
    "                .map { it.split(\",\").map(String::toInt) }\n",
    "        }\n",
    "        .toMutableList()\n",
    "    \n",
    "    val n = scanners.size\n",
    "    val positions = Array(n) { IntArray(3) }\n",
    "    val fixed = BooleanArray(n)\n",
    "    fixed[0] = true\n",
    "    \n",
    "    fun overlap(i: Int, j: Int): Boolean {\n",
    "        val si = scanners[i].toSet()\n",
    "        \n",
    "        for (p in listOf(listOf(0, 1, 2), listOf(0, 2, 1), listOf(1, 0, 2), listOf(1, 2, 0), listOf(2, 0, 1), listOf(2, 1, 0)))\n",
    "            for (c in listOf(listOf(-1, -1, -1), listOf(-1, -1, 1), listOf(-1, 1, -1), listOf(-1, 1, 1), listOf(1, -1, -1), listOf(1, -1, 1), listOf(1, 1, -1), listOf(1, 1, 1))) {\n",
    "                val t = scanners[j].map {\n",
    "                    beacon -> (0..2).map { c[it] * beacon[p[it]] }\n",
    "                }\n",
    "                \n",
    "                for (u in scanners[i])\n",
    "                    for (v in t) {\n",
    "                        val tt = t.map {\n",
    "                            beacon -> (0..2).map { beacon[it] - (v[it] - u[it]) }\n",
    "                        }\n",
    "                        val sij = tt.toSet().intersect(si)\n",
    "                        \n",
    "                        if (sij.size >= 12) {\n",
    "                            fixed[j] = true\n",
    "                            scanners[j] = tt\n",
    "                            positions[j] = (0..2).map { v[it] - u[it] }.toIntArray()\n",
    "                            return true\n",
    "                        }\n",
    "                    }\n",
    "            }\n",
    "        \n",
    "        return false\n",
    "    }\n",
    "    \n",
    "    for (t in 0 until n - 1) {\n",
    "        var found = false\n",
    "        \n",
    "        for (i in 0 until n) {\n",
    "            if (!fixed[i]) continue\n",
    "            for (j in 0 until n) {\n",
    "                if (fixed[j]) continue\n",
    "                if (overlap(i, j)) {\n",
    "                    found = true\n",
    "                    break\n",
    "                }\n",
    "            }\n",
    "            if (found) break\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    var beacons = scanners[0].toSet()\n",
    "    for (i in (1 until n))\n",
    "        beacons = beacons.union(scanners[i].toSet())\n",
    "    val numberOfBeacons = beacons.size\n",
    "    \n",
    "    var maxDistance = 0\n",
    "    for (u in positions)\n",
    "        for (v in positions)\n",
    "            maxDistance = maxDistance.coerceAtLeast((0..2).map { abs(u[it] - v[it]) }.sum())\n",
    "    \n",
    "    return Pair(numberOfBeacons, maxDistance).toString()\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "879d7d4b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(79, 3621)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(sample)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "392d9459",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(440, 13382)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(input)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Kotlin",
   "language": "kotlin",
   "name": "kotlin"
  },
  "language_info": {
   "codemirror_mode": "text/x-kotlin",
   "file_extension": ".kt",
   "mimetype": "text/x-kotlin",
   "name": "kotlin",
   "nbconvert_exporter": "",
   "pygments_lexer": "kotlin",
   "version": "1.6.20-dev-6372"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
